package leetcode.editor.cn;

//给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。 
//
// 
//
// 示例 1： 
//
// 
//输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
//输出：[1,2,4,7,5,3,6,8,9]
// 
//
// 示例 2： 
//
// 
//输入：mat = [[1,2],[3,4]]
//输出：[1,2,3,4]
// 
//
// 
//
// 提示： 
//
// 
// m == mat.length 
// n == mat[i].length 
// 1 <= m, n <= 10⁴ 
// 1 <= m * n <= 10⁴ 
// -10⁵ <= mat[i][j] <= 10⁵ 
// 
// Related Topics 数组 矩阵 模拟 👍 243 👎 0

//Java：对角线遍历
public class DiagonalTraverse_498{
    public static void main(String[] args) {
        Solution solution = new DiagonalTraverse_498().new Solution();
        // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int m=mat.length, n=mat[0].length;
        int[] res = new int[m*n];
        int i=0,j=0,count=0;
        for (int k = 0; k < m+n-1; k++) {
            int l = 0;
            while(i>=0 && i<m && j>=0 && j<n){
                System.out.println(count+"-"+i+"-"+j);
                res[count++] = mat[i][j];
                if(k % 2 == 0){
                    i--;
                    j++;
                }else{
                    i++;
                    j--;
                }
                if(i>=m) j++;
                if(j>=n) i++;
            }
            if(i<0) i++;
            if(j<0) j++;
            if(i>=m) {i--;j++;}
            if(j>=n) {j--;i++;}

        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
